/*
那我就问个简单的吧,
一个大小11的数组,
里面存放的是从1－10这10个数字，
其中有一个数重复了,
找出是哪个数重复了?
用了二十分钟,还是 O(n2) 的.
*/

#include "junix.h"
using namespace std;

//solution 1
uint64_t f(uint64_t v[], uint64_t size) {
	uint64_t sum = std::accumulate(v,v+size,0);
	return sum - 55;
}

//solution 2
uint64_t g(uint64_t v[], uint64_t size) {
	for (uint64_t i=0;i<size;i++) {
		if (v[i]==i+1) {
			continue;
		} else {
			if (v[v[i]-1]==v[i]) {
				return i;
			} else {
				std::swap(v[i],v[v[i]-1]);
			}
		}
	}

	assert(true);
	return 0;
}

int main(int argc, char **argv)
{
	uint64_t v[]={1,4,2,3,4,5,6,7,8,9,10};
	std::cout<<f(v,sizeof(v)/sizeof(v[0]))<<std::endl;
	std::cout<<g(v,sizeof(v)/sizeof(v[0]))<<std::endl;
}
